﻿#pragma once
#include "stdafx.h"

/*
电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。



示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题方式，这个题会让我想到hashmap，或者直接打表，然后找到后，遍历值，解出所有可能解。
遍历方式，可以采用回溯法(DFS)，或者采用队列(BFS)
*/

//回溯法
void callBackStr(vector<string>& strs, const unordered_map<char, string>& phoneMap,
	const string & digits, int index, string &str)
{
	if (index == digits.length())
	{
		strs.push_back(str);
	}
	else
	{
		char digit = digits[index];
		const string &letters = phoneMap.at(digit);
		for (const char &letter : letters)
		{
			str.push_back(letter);
			callBackStr(strs, phoneMap, digits, index + 1, str);
			str.pop_back();
		}
	}
}


vector<string> letterCombinations(string digits) 
{
	vector<string> strs; //要返会的结果
	if (digits.empty())
	{
		return strs;
	}
	unordered_map<char, string> phoneMap{
		{'2',"abc"},
		{'3',"def"},
		{ '4', "ghi" },
		{ '5', "jkl" },
		{ '6', "mno" },
		{ '7', "pqrs" },
		{ '8', "tuv" },
		{ '9', "wxyz" }
	};
	string str;
	callBackStr(strs,phoneMap,digits,0,str);
	return strs;
}


//BFS  采用队列的方式
vector<string> letterCombinations2(string digits)
{
	vector<string> strs; //要返会的结果
	if (digits.empty())
	{
		return strs;
	}
	unordered_map<char, string> phoneMap{
		{ '2',"abc" },
		{ '3',"def" },
		{ '4', "ghi" },
		{ '5', "jkl" },
		{ '6', "mno" },
		{ '7', "pqrs" },
		{ '8', "tuv" },
		{ '9', "wxyz" }
	};
	//申请队列
	queue<string> que;
	for (int i =0; i< phoneMap[digits[0]].size(); ++i)
	{
		string str;
		str.push_back(phoneMap[digits[0]][i]);
		que.push(str);
	}

	string str1 = ""; //存储对头元素
	for (int i = 1; i < digits.size(); ++i)
	{
		int length = que.size();
		while (length --)
		{
			for (int j = 0; j < phoneMap[digits[i]].size(); j++)
			{
				str1 = que.front();
				str1 = str1 + phoneMap[digits[i]][j];
				que.push(str1);
			}
			que.pop();//
		}
	}

	while (!que.empty())
	{
		strs.push_back(que.front());
		que.pop();
	}
	return strs;
}